Waga

Limit pamięci: 32 MB

To zadanie pojawiło się równolegle na finale IX OI. Polecamy wysyłać rozwiązania do tamtego zadania, to zostanie wkrótce usunięte z serwisu.

Mamy do dyspozycji wagę szalkową. Waga znajduje się w stanie równowagi wtedy i tylko wtedy, gdy obie szalki są puste lub gdy sumy mas odważników na obu szalkach są takie same. W danym zbiorze odważników należy znaleźć takie dwa rozłączne podzbiory, aby po położeniu wszystkich odważników z jednego z nich na jednej szalce, natomiast wszystkich odważników z drugiego zbioru na drugiej szalce, waga znalazła się w stanie równowagi. Ponadto spośród wszystkich układów odważników, dla których waga jest w równowadze, należy wybrać ten, który zawiera odważnik o maksymalnej możliwej masie. W przypadku wielu takich rozwiązań trzeba podać tylko jedno z nich.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia masy dostępnych odważników,
• wyznaczy dwa rozłączne zbiory odważników spełniające warunki zadania,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita , , równa liczbie dostępnych odważników. W każdym z następnych wierszy znajduje się po jednej dodatniej liczbie całkowitej równej masie jednego odważnika za zbioru dostępnych odważników. Można założyć, że łączna masa odważników nie przekracza .

Wyjście

W pierwszym wierszu standardowego wyjścia należy zapisać dwie nieujemne liczby całkowite i oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę odważników w pierwszym i w drugim zbiorze. W drugim wierszu powinno się znaleźć liczb całkowitych oddzielonych pojedynczymi odstępami. Powinny to być masy odważników z pierwszego zbioru. Natomiast w trzecim wierszu powinno zostać wypisanych liczb całkowitych odzielonych pojedynczymi odstępami i równych masom odważników w drugim zbiorze.

Przykład

Dla danych wejściowych:

4
1
1
2
7

Dla danych wejściowych:

2 1
1 1
2